#include <bits/stdc++.h>

using namespace std;

class Solution
{
public:
    //@ysh's method
    // static bool cmp(vector<int> &a, vector<int> &b)
    // {
    //     return a[0] < b[0];
    // }
    // int eraseOverlapIntervals(vector<vector<int>> &intervals)
    // {
    //     sort(intervals.begin(), intervals.end(), cmp);
    //     int delete_count = 0;
    //     int length = intervals.size();
    //     for (int i = 1; i < length; i++)
    //     {
    //         if (intervals[i][0] >= intervals[i - 1][1])
    //         {
    //             continue;
    //         }
    //         else if (intervals[i][1] <= intervals[i - 1][1])
    //         {
    //             delete_count++;
    //         }
    //         else
    //         {
    //             delete_count++;
    //             intervals[i][1] = intervals[i - 1][1];
    //         }
    //     }
    //     return delete_count;
    // }

    // book's method
    static bool cmp(vector<int> &a, vector<int> &b)
    {
        return a[1] < b[1];
    }
    int eraseOverlapIntervals(vector<vector<int>> &intervals)
    {
        sort(intervals.begin(), intervals.end(), cmp);
        int count = 1;
        int end = intervals[0][1];
        for (size_t i = 1; i < intervals.size(); i++)
        {
            if (end <= intervals[i][0])
            {
                count++;
                end = intervals[i][1];
            }
        }
        return intervals.size() - count;
    }
};

int main()
{
    vector<vector<int>> intervals{{1, 2},
                                  {2, 3},
                                  {3, 4},
                                  {1, 3}};
    Solution sol;
    cout << sol.eraseOverlapIntervals(intervals) << endl;
    return 0;
}